package nowcoder;
/**
 * 36939-合法括号序列判断
 * 链接：https://www.nowcoder.com/practice/d8acfa0619814b2d98f12c071aef20d4?tpId=8&&tqId=11039&rp=1&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking
 */
import java.util.*;
public class Day07_2 {
    public static void main(String[] args) {
        System.out.println(chkParenthesis("(()())", 6));
    }
    public static boolean chkParenthesis(String A, int n) {
        //先看特殊情况
        if(A.charAt(0) != '(' || A.charAt(n-1) != ')' || n % 2 != 0){
            return false;
        }

        Deque<Character> stack = new ArrayDeque<>();
        for (int i = 0; i < A.length(); i++) {
            char c = A.charAt(i);
            if(c != '(' && c != ')'){
                return false;
            }else if(c == '('){
                stack.push(c);
            }else if(stack.peek() == '('){
                //当前符号是')' 且 上一个括号是'('
                stack.pop();
            }else{
                return false;
            }
        }
        return stack.isEmpty();
    }
}
